#include <stdio.h>
#include <stdlib.h>

/*
 * AOV： DAG  拓扑排序,检查AOV网有无环 
 */

#define vertex 5
#define edge 6

struct link
{
  int data;
  struct link * next;
};

struct graph
{
  struct link a[vertex+1];
};

void adjacency(struct graph * graph)
{
  int i, j, k;
  struct link * src;

  for (i = 1; i <= vertex; i++) {
    graph->a[i].data = 0;
    graph->a[i].next = NULL;
  }

  for (k = 1; k <= edge; k++) {
    printf("input a edge:\n");
    scanf("%d %d", &i, &j);

    src = (struct link *) malloc (sizeof(struct link));
    src->data = j;
    src->next = graph->a[i].next;
    graph->a[i].next = src;
    graph->a[i].data++;
  }
}

void topsort(struct graph * graph)
{
  int top = 0, m = 0;
  int i, k;
  struct link * src;

  for (i = 1; i <= vertex; i++)
    if (graph->a[i].data == 0) {
      graph->a[i].data = top;
      top = i;
    }

  while (top > 0) {
    i = top;
    top = graph->a[top].data;
    printf(" %d ", i);
    m++;

    src = graph->a[i].next;
    while (src != NULL) {
      k = src->data;
      graph->a[k].data--;
      
      if (graph->a[k].data == 0) {
	graph->a[k].data = top;
	top = k;
      }

      src = src->next;
    }
  }

  if (m < vertex)
    printf("网络中出现回环.\n");
}

void main()
{
  struct graph graph;

  adjacency(&graph);
  topsort(&graph);
}

